package structs;

import java.util.HashSet;
import java.util.Set;
import java.util.TreeMap;

/**
 * 力扣测试
 *
 * @author panshao
 * @CREATE 2019/5/23
 */
public class LeetCodeTest {
    public static void main(String[] args) {
       //  boolean palindrome = isPalindrome(10);
      /* int[] arr = {1,8,6,2,5,4,8,3,7};
        int area = maxArea(arr);*/
        String result = longestPalindrome("ccc");

    }

    /**
     * 9.是否回文数
     * @param x
     * @return
     */
    public static boolean isPalindrome(int x) {
        if(x < 0){
            return false;
        }

        int[] arr = new int[32];
        int p = x, q = 0, i=0;
        while(p != 0){
            q = p%10;
            p = p/10;
            arr[i++] = q;
        }

        int k = i/2;
        boolean ret = true;
        for(int j=0; j<k; j++){
            if(arr[j] != arr[i-j-1]){
                ret = false;
                break;
            }
        }
        return ret;
    }

    /**
     * 11.坐标最大面积
     * @param height
     * @return
     */
    public static int maxArea(int[] height) {
        TreeMap<Integer,Integer> a = new TreeMap<>();
        for(int i=0; i<height.length; i++){
            a.put(i+1, height[i]);
        }

        Set<String> pair = new HashSet<>();
        int area = 0;
        for(Integer key_1 : a.keySet()){
            for(Integer key_2 : a.keySet()){
                if(key_1.equals(key_2)){
                    continue;
                }
                if(pair.contains(key_1 + "#" + key_2) == true || pair.contains(key_2+ "#" + key_1) == true){
                    continue;
                }
                pair.add(key_1 + "#" + key_2);
                int temp = Math.abs(key_1 - key_2)*Math.min(a.get(key_1), a.get(key_2)) ;
                area =  temp > area ? temp:area;
            }
        }

        return area;
    }

    /**
     * 5，最长回文字符串
     * @param s
     * @return
     */
    public static String longestPalindrome(String s) {
        if(s == null && "".equals(s)){
            return "";
        }

        if(s.length() == 1){
            return s;
        }

        String result = "";
        Boolean[][] record = new Boolean[s.length()][s.length()];
        // 先找出所以1个字符，
        for(int i=0; i<s.length(); i++){
            record[i][i] = true;
            result = s.substring(i, i+1);
        }

        // 2个字符的回文
        for(int i=0; i < s.length() -1 ;i++){
            record[i][i+1] = s.charAt(i) == s.charAt(i+1);
            if(record[i][i+1]){
                result = s.substring(i, i+1+1);
            }
        }


        // 找出3个及3个以上字符的回文
        for(int k=3; k<=s.length(); k++){
            for(int j=0; (j+k) <= s.length(); j++){
                record[j][j+k-1] = record[j+1][j+k-1-1] && (s.charAt(j) == s.charAt(j+k-1));
                if(record[j][j+k-1]){
                    result = s.substring(j, j+k);
                }
            }
        }

        return result;

    }
}
